/**
 * created by 文阿花, 2021/4/20
 * Copyright (c) 2021, 416143467@qq.com All Rights Reserved.
 * #                   *********                            #
 * #                  ************                          #
 * #                  *************                         #
 * #                 **  ***********                        #
 * #                ***  ****** *****                       #
 * #                *** *******   ****                      #
 * #               ***  ********** ****                     #
 * #              ****  *********** ****                    #
 * #            *****   ***********  *****                  #
 * #           ******   *** ********   *****                #
 * #           *****   ***   ********   ******              #
 * #          ******   ***  ***********   ******            #
 * #         ******   **** **************  ******           #
 * #        *******  ********************* *******          #
 * #        *******  ******************************         #
 * #       *******  ****** ***************** *******        #
 * #       *******  ****** ****** *********   ******        #
 * #       *******    **  ******   ******     ******        #
 * #       *******        ******    *****     *****         #
 * #        ******        *****     *****     ****          #
 * #         *****        ****      *****     ***           #
 * #          *****       ***        ***      *             #
 * #            **       ****        ****                   #
 */
package com.light.mytext.javaknowledge.datastructure;

import android.util.Log;

/**
 * 描 述：单链表
 * 作 者：文阿花  2021-04-20 16:04
 * 修改描述：
 * 修 改 人：
 * 修改版本：
 */
public class SingleLinkTable<T> {


    public class Node {
        private T t;
        private Node next;

        public Node(T t, Node next) {
            this.t = t;
            this.next = next;
        }

        public Node(T t) {
            this.t = t;
        }

    }

    public Node head;//头结点
    public int size;

    //构造函数
    public SingleLinkTable(Node head, int size) {
        this.head = null;
        this.size = 0;
    }

    public SingleLinkTable() {
    }

    /**
     * 操作方法
     *
     * @return
     */
    //获取链表元素的个数
    public int getSize() {
        return this.size;
    }

    //判断链表是否为空
    public boolean isEmpty() {
        return this.size == 0;
    }

    //链表头部添加元素
    public void addHead(T t) {
        Node note = new Node(t);
        note.next = this.head;
        this.head = note;
        this.size++;
    }

    //向链表尾部插入元素
    public void addLast(T t) {
        this.add(t, this.size);
    }

    //向链表中添加元素
    public void add(T t, int index) {
        if (index < 0 || index > this.size) {
            throw new IllegalArgumentException("index is error");
        }
        if (index == 0) {
            this.addHead(t);
            return;
        }
        Node nodehead = this.head;//找到头节点
        //找到要插入节点的前一个节点
        for (int i = 0; i < index - 1; i++) {
            nodehead = nodehead.next;
        }
        Node node = new Node(t);//要插入的节点
        //要插入的节点的下一个节点指向nodehead节点的下一个节点
        node.next = nodehead.next;
        //nodehead的下一个节点指向要插入的节点node
        nodehead.next = node;
        this.size++;
    }

    //删除链表元素
    public void remove(T t) {
        if (this.head == null) {
            Log.i("SingleLinkTable==", "无可删除元素");
            return;
        }
        //要删除的元素与头结点的元素相同
        while (head != null && head.t.equals(t)) {
            head = head.next;
            this.size--;
        }
        //要删除的元素和除头结点外的其他节点元素相同
        Node currentNode = this.head;
        while (currentNode != null && currentNode.next != null) {
            if (currentNode.next.t.equals(t)) {
                currentNode.next = currentNode.next.next;
                this.size--;
            } else {
                currentNode = currentNode.next;
            }
        }
    }

    //删除链表的第一个元素
    public T removeFirst() {
        if (this.head == null) {
            Log.i("SingleLinkTable==", "无可删除元素");
            return null;
        }
        Node delNode = this.head;
        this.head = this.head.next;
        delNode.next = null;//不太懂呀
        this.size--;
        return delNode.t;
    }

    //判断链表中是否包含某个元素
    public boolean isContains(T t) {
        Node current = this.head;
        while (current != null) {
            if (current.t.equals(t)) {
                return true;
            } else {
                current = current.next;
            }

        }
        return false;
    }

    public String ToSting() {
        StringBuffer sb = new StringBuffer("");
        Node current = this.head;
        while (current != null) {
            sb.append(current.t + ",");
            current = current.next;
        }
        sb.append("NULL");
        return sb.toString();
    }


    /**
     * 打印
     */
    public void logMess() {
        Log.i("LinkTableActivity==", this.ToSting());
    }
}
